BZOJ3747【POI2015】Kinoman <线段树>

Problem

【POI2015】Kinoman

Description

共有部电影，编号为，第部电影的好看值为。
在天之中（从编号）每天会放映一部电影，第天放映的是第部。
你可以选择，并观看第天内所有的电影。
如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。
你希望最大化观看且仅观看过一次的电影的好看值的总和。

Input

第一行两个整数。
第二行包含个整数。
第三行包含个整数。

Output

输出观看且仅观看过一次的电影的好看值的总和的最大值。

Sample Input

1
2
3

9 4
2 3 1 1 4 1 2 4 1
5 3 6 6

Sample Output

Explanation

观看第天内放映的电影，其中看且仅看过一次的电影的编号为。

Source

鸣谢Jcvb

标签：线段树

Solution

暴力枚举左端点，考虑用线段树动态维护此时每个点作为右端点的答案的最大值。
先对每天预处理后面最早哪一天会放同样的电影，若后面不会再放，则令其为。这个数组称为。每种电影最先放映的时间称为（这是由于从后往前预处理，最先放映的在最后扫到）。
开始时，以作为左端点，对于电影，右端点在时对答案有贡献，于是区间整体加。此后每次将左端点向后移一天。设当前为第天，则移到后，区间不会再有电影的贡献，于是区间整体减。而区间则会有电影的贡献，于是区间区间加。
每次移动左端点，并在线段树上修改，到下一个左端点后得到一个答案并和最大值打擂即可。时间复杂度。

Code

#include <bits/stdc++.h>
#define MAX_N 1000000
#define mid ((s+t)>>1)
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, f[MAX_N+5], w[MAX_N+5];
int pos[MAX_N+5], nxt[MAX_N+5], cnt[MAX_N+5];
lnt tr[MAX_N<<2], tag[MAX_N<<2], ans;
void update(int v) {tr[v] = max(tr[v<<1], tr[v<<1|1]);}
void downtag(int v) {
    if (!tag[v]) return;
    tr[v<<1] += tag[v], tr[v<<1|1] += tag[v];
    tag[v<<1] += tag[v], tag[v<<1|1] += tag[v];
    tag[v] = 0;
}
void modify(int v, int s, int t, int l, int r, lnt x) {
    if (s >= l && t <= r) {tr[v] += x, tag[v] += x; return;}
    downtag(v);
    if (l <= mid) modify(v<<1, s, mid, l, r, x);
    if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r, x);
    update(v);
}
int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(f[i]);
    for (int i = 1; i <= m; i++) read(w[i]);
    for (int i = n; i; i--) nxt[i] = pos[f[i]], pos[f[i]] = i;
    for (int i = 1; i <= m; i++) if (pos[i]) {
        if (!nxt[pos[i]]) modify(1, 1, n, pos[i], n, w[i]);
        else modify(1, 1, n, pos[i], nxt[pos[i]]-1, w[i]);
    }
    for (int i = 1; i <= n; i++) {
        ans = max(ans, tr[1]);
        if (nxt[i]) {
            modify(1, 1, n, i, nxt[i]-1, -w[f[i]]);
            if (!nxt[nxt[i]]) modify(1, 1, n, nxt[i], n, w[f[i]]);
            else modify(1, 1, n, nxt[i], nxt[nxt[i]]-1, w[f[i]]);
        } else modify(1, 1, n, i, n, -w[f[i]]);
    }
    return printf("%lld\n", ans), 0;
}